package 动态规划.递归参数思考型;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/7/11 8:17
 */
public class lc1911最大子序列交替和 {

    /*
     f(index, state) :表示 当前 从 index ~ len 区间内 ,状态 为 state 的时候的最大值. ( state 表示 当前nums[index]元素下标 处于 奇数位 还是偶数位)
     */
    public int recursion(int index,int state,int nums[]){
        if(index == nums.length){
            return 0;
        }
        // no choose
        int ans = recursion(index + 1,state,nums);
        int ans1 = 0;

        // choose
//        ans = Math.max(recursion(index + 1,state,nums)+(state & 1) == 0 ? nums[index] : - nums[index],ans);
        if(state == 0){ // 偶数下标
            ans1 = recursion(index + 1,1,nums) + nums[index];
        }else{ //state = 1 表示 是 奇数下标
            ans1 = recursion(index + 1,0,nums)  - nums[index];
        }
        return Math.max(ans,ans1);
    }



    // dp

    public int dp(int nums[]){
        int dp[][] = new int[nums.length + 1][2];
//        dp[nums.length][] = 0;
        for(int index = nums.length - 1;index >=0 ;index--){
            dp[index][0] = Math.max(dp[index + 1][0],dp[index + 1][1] + nums[index]);
            dp[index][1] = Math.max(dp[index + 1][1],dp[index + 1][0] - nums[index]);
        }
        return dp[0][0];
    }

}
